/**
//给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 
//
// 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
//输出：3
//解释：和等于 8 的路径有 3 条，如图所示。
// 
//
// 示例 2： 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：3
// 
//
// 
//
// 提示: 
//
// 
// 二叉树的节点个数的范围是 [0,1000] 
// -10⁹ <= Node.val <= 10⁹ 
// -1000 <= targetSum <= 1000 
// 
// Related Topics 树 深度优先搜索 二叉树 👍 1160 👎 0

*/

package com.xixi.dataStructure.tree.binaryTree;

import com.xixi.dataStructure.tree.TreeNode;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class ID00437PathSumIii {
public static void main(String[] args) {
Solution solution = new ID00437PathSumIii().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int pathNum = 0;
    public int pathSum(TreeNode root, int targetSum) {
        deepSearch(root, null, targetSum);
        return pathNum;
    }

    public void deepSearch(TreeNode node, long[] preFixes, int targetSum){
        if(node == null) return;
        //循环所有路径可能，去匹配当前节点的值是否满足target
        if(node.val == targetSum){ //当前路径为一个节点也可能满足
            ++pathNum;
        }
        long[] nextLevelPreFixes;
        if(preFixes == null){ //首节点
            nextLevelPreFixes= new long[] {node.val};
        }else{
            nextLevelPreFixes = new long[preFixes.length + 1];
            for(int i = 0; i < preFixes.length; ++i){
                long nowPathSum = preFixes[i] + node.val;
                if(nowPathSum == targetSum){ //有路经满足就+1
                    ++pathNum;
                }
                nextLevelPreFixes[i] = nowPathSum; //下一层节点的preFix需要加上这一层节点
            }
            nextLevelPreFixes[preFixes.length] = node.val;
        }

        //递归检测
        deepSearch(node.left, nextLevelPreFixes, targetSum);
        deepSearch(node.right, nextLevelPreFixes, targetSum);

    }

    int count = 0;

    private Map<Long, Integer> traversal(TreeNode node, long targetSum) {
        if (node == null) return Collections.emptyMap();

        Map<Long, Integer> leftMap = traversal(node.left, targetSum);
        Map<Long, Integer> rightMap = traversal(node.right, targetSum);
        Map<Long, Integer> childSum = new HashMap<>(); //包含当前节点，可以有多少种sum可能

        long nodeVal = node.val;
        childSum.put(nodeVal, 1);

        for (Map.Entry<Long, Integer> entry : leftMap.entrySet()) {

            long newSumInt = entry.getKey() + nodeVal; //新key
            int newValue = entry.getValue(); //childkey的可能条数

            if (childSum.containsKey(newSumInt)) { //包含新值 等于已存在的可能性 + 当前的可能性
                newValue = childSum.get(newSumInt) + newValue;
            }

            childSum.put(newSumInt, newValue);
        }

        for (Map.Entry<Long, Integer> entry : rightMap.entrySet()) {

            Long newSumInt = entry.getKey() + nodeVal; //新key
            int newValue = entry.getValue(); //childkey的可能条数

            if (childSum.containsKey(newSumInt)) { //包含新值 等于已存在的可能性 + 当前的可能性
                newValue = childSum.get(newSumInt) + newValue;
            }

            childSum.put(newSumInt, newValue);
        }

        if (childSum.containsKey(targetSum)) {
            count += childSum.get(targetSum);
        }

        return childSum;
    }

}
//leetcode submit region end(Prohibit modification and deletion)




}